// Created by WXX on 2021/11/29 10:17
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * 执行用时：420 ms, 在所有 C++ 提交中击败了49.26%的用户
 * 内存消耗：8.6 MB, 在所有 C++ 提交中击败了54.07%的用户
 */
// 写法一
class Solution {
public:

    struct Node {
        double  val;
        int a, b;  // val = arr[a] / arr[b]

        bool operator< (const Node &t) const {
            return val > t.val;  // 小顶堆
        }
    };

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {

        int n = arr.size();
        priority_queue<Node> heap;
        for (int i = 0; i + 1 < n; i++)
            heap.push({arr[i] * 1.0 / arr.back(), i, n - 1});

        for (int i = 0; i < k - 1; i++) {
            auto t = heap.top(); heap.pop();
            int a = t.a, b = t.b;
            if (a != b - 1) heap.push({arr[a] * 1.0 / arr[b - 1], a, b - 1});
        }
        auto t = heap.top();
        vector<int> res = {arr[t.a], arr[t.b]};
        return res;
    }
};

/*
// 写法二
class Solution {
public:

    struct Node {
        double  val;
        int a, b;  // val = arr[a] / arr[b]

        bool operator> (const Node &t) const {
            return val > t.val;  // 小顶堆
        }
    };

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {

        int n = arr.size();
        priority_queue<Node, vector<Node>, greater<Node>> heap;
        for (int i = 0; i + 1 < n; i++)
            heap.push({arr[i] * 1.0 / arr.back(), i, n - 1});

        for (int i = 0; i < k - 1; i++) {
            auto t = heap.top(); heap.pop();
            int a = t.a, b = t.b;
            if (a != b - 1) heap.push({arr[a] * 1.0 / arr[b - 1], a, b - 1});
        }
        auto t = heap.top();
        vector<int> res = {arr[t.a], arr[t.b]};
        return res;
    }
};
 */

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> arr = {1, 2, 3, 5};
    OutputBasicArray1D(Solution().kthSmallestPrimeFraction(arr, 3));

    return 0;
}
